package hot;

import java.util.Arrays;

public class siyi {
//    https://leetcode.cn/problems/first-missing-positive/?envType=study-plan-v2&envId=top-100-liked

        public static int firstMissingPositive(int[] nums) {
            Arrays.sort(nums);
            for(int i=1;i<=nums.length;i++){
                int res=binarySearch(nums,i);
                if(res==-1){
                    return i;
                }
            }
            return nums.length+1;
        }
        public static int binarySearch(int[] nums,int target){
            int left=0;
            int right=nums.length-1;
            while(left<=right){
                int mid=left+(right-left)/2;   //防止整数溢出
                if(nums[mid]==target){
                    return target;
                }else if(nums[mid]>target){
                    right=mid-1;
                }else{
                    left=mid+1;
                }
            }
            return -1;
        }
        //法二：
    //时 ：O（N） 空：O（1）
    class Solution {
        public int firstMissingPositive(int[] nums) {
            int n=nums.length;
            for(int i=0;i<n;i++){
                if((i+1)==nums[i]){
                    continue;
                }
                int x=nums[i];
                if(x>=1&&x<=n&&x!=nums[x-1]){
                    swap(nums,i,x-1);
                    i--; // 抵消后面的i++
                }
            }
            for(int  i=0;i<n;i++){
                if((i+1)!=nums[i]){
                    return i+1;
                }
            }
            return n+1;
        }
        public void swap(int[] nums,int i,int j){
            int tmp=nums[i];
            nums[i]=nums[j];
            nums[j]=tmp;
        }
    }

    public static void main(String[] args) {
        int[] nums={1,2,0};
        int i = firstMissingPositive(nums);
        System.out.println(i);

    }

    }

